package com.stefan.lru;

import java.util.HashMap;
import java.util.Map;

//LRU的优化版本，双向链表 + Map(实际上这里是用到了Map里面数组的功能，当然也可以直接用数组)
public class LRUCacheAdvanced<K,V> {
    private final int capacity;
    private final Map<K,Node<K,V>> map;
    private final Node<K,V> head,tail;

    static class Node<K,V> {
        K key;
        V value;
        Node<K,V> prev;
        Node<K,V> next;
        Node(){}
        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    public LRUCacheAdvanced() {
        this.capacity = 10;
        this.map = new HashMap<>();
        head = new Node<K,V>();
        tail = new Node<K,V>();
        head.next = tail;
        tail.prev = head;
    }
    public V get (K key) {
        Node<K, V> node = map.get(key);
        if (node == null) {
            return null;
        }
        moveToHead(node);
        return node.value;
    }

    public void put (K key,V value) {
        Node<K, V> node = map.get(key);
        if (node == null) {
            node = new Node<>(key,value);
            //step1 put to map
            map.put(key,node);
            //step2 add to head
            addToHead(node);
            //step3 LRU - check the capacity, remove the tail if > capacity
            if (map.size()>capacity) {
                Node<K, V> removed = removeTail();
                map.remove(removed.key);
            }
        } else {
            //step1 update map with new value
            node.value = value;
            //step2 move to head (delete from linked list and add to head)
            moveToHead(node);
        }
    }

    public void moveToHead(Node<K,V> node) {
        removeNode(node);
        addToHead(node);
    }

    //头插法
    public void addToHead (Node<K,V> node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }


    public void removeNode (Node<K,V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node.prev = null;
        node.next = null;
    }

    public Node<K,V> removeTail () {
        Node<K, V> node = tail.prev;
        removeNode(node);
        return node;
    }
}
